1. Field of the Invention
This invention is in the field of methods and apparatus for producing the product of a multiplier and a multiplicand where the multiplier, multiplicand and product are each a residue with respect to a check base m, where m=(2.sup.b -1), and b is the number of bits of a residue. Such methods and apparatus are used in the binary and arithmetic units of digital data processing systems to check the accuracy of multiplying two operands.
2. Description of the Prior Art
To assure the accuracy of arithmetic operations on binary numbers in digital data processors, there is a need to validate such operations. Various ways of doing this have been developed, such as by parallel execution of the same operation on the same operands, or by the use of parity checks at each stage of an operation. Another way to validate the accuracy of arithmetic operations such as multiplication of binary numbers is to validate each such operation using residue theory mathematics in which the residue (r) of a number, or operand, "X" is the remainder resulting from the division of "X" by the check base "m", or EQU X=km+r.
In the foregoing, k is an integer constant such that r is equal to or greater than 0 and less than m. A common representation of this definition is EQU r=.vertline.X.vertline..sub.m.
Any arithmetic operation .phi. performed on two operands A and B produces a resultant R which can be represented as R=.phi. (A,B). The basic residue theory check equation is that EQU .vertline.R.vertline..sub.m =.phi..vertline..vertline.A.vertline..sub.m, .vertline.B.vertline..sub.m .vertline..sub.m.
Thus, the residue of the resultant R is equal to the operation .phi., multiplication, for example, performed on the residues of the operands, in this case multiplier and multiplicand A and B. The multiplication operation .phi. performed on the residues of multiplier A and multiplicand B is defined as being executed in modulo m arithmetic. The significance of the foregoing is that, if the two operands are multiplied, then the residue of the result of that multiplication, the residue of the product, will equal the residue of the result, or product, of the multiplication performed on the residues of the two operands, it being a requirement that all residues are determined with respect to the same check base m. Residue checking has the advantage that it will detect all single bit errors in the resultant R.
From the foregoing, it is apparent that there is a need for a multiplier modulo with respect to a given check base "m". Typically, this type of multiplication is accomplished by means of a table look-up method using a read only memory (ROM) device in which the address is composed of the residues of the multiplier and the multiplicand each of b bits, and in the addressed location there is stored the residue of the product of the multiplier and the multiplicand all to the same check base m, where m=(2.sup.b -1). In the foregoing equation, b is an integer, and is the number of bits in each residue.
Since there is always pressure to reduce costs and increase the speed of all operations performed by digital data processing systems, there is a need to implement methods and apparatus which minimize the size of the random access memory required to store the residues of the products of two residues to reduce the cost of implementation, other factors remaining the same, as well as to produce the residue of the product of any given multiplier and multiplicand which are also residues with respect to the check base m, as quickly and as reliably as possible.